In the field of object-oriented programming, data structures known as "objects" that are instances of particular classes (or types) are created, manipulated and deleted during the course of either compilation of or during the execution of an object-oriented program. A given object may have various types associated with it. For example, the class of which the object is an instance is termed the dynamic type. The type of the pointer through which the object is being accessed is called the static type, and the type of a class that the object might inherit from is termed the target type. Typically, target type refers to the class to which the object is being cast, as will be explained below. These different types are useful in describing the manipulation of a particular object.
FIG. 1 illustrates symbolically a prior art class hierarchy tree 10 for classes A1, A2 and B. This example helps illustrate use of terminology for different types. FIG. 1 shows defined classes A1 20, A2 40 and B 30. Class A1 has defined instance variables (known as members in the C++ object-oriented programming language) I 22 and J 24. Also defined are methods (known as member functions in C++) F 26 and G 28. Class B30 has been defined as a subclass (known as a derived class in C++) of class A1. Defined upon class B is instance variable K 32 and methods F, H and Y, respectively 34, 36 and 38. In this example, method F 34 defined upon class B overrides method F 26 that is defined upon class A1. In other words, when objects that are instances of class B call method F, they will be invoking method F 34 that is defined upon class B which may be different from method F 26 defined upon class A I. This ability known as "overloading" to override methods or instance variables in sub-classes is an important feature of object-oriented programming.
For those object-oriented languages that support multiple inheritance, a class A2 40 may be defined that is also a parent class of class B along with class A1. In this example, class A2 defines instance variables M 42 and N 44, along with methods X and Y, 46 and 48, respectively. Method Y 38 defined upon class B overrides method Y 48 defined upon class A2. Thus, class hierarchy 10 defines a class B having parent classes A1 and A2. Objects of class B will inherit all instance variables and methods of classes A1, A2 and class B, with methods F and Y of class B overriding the respective methods of classes A1 and A2.
In such a situation, it often occurs that a pointer of the type A1 points to an object of class B. In this situation, the static type is of type A1, because that is the type of the pointer. However, the dynamic type is of type B, because that is the actual class of the object. If it is desirable to know if the object inherits from any class present in the class hierarchy, then that class which is the potential type of the object is called the target type. However, if an A1 pointer is used to point to an object of class B, then instance variable K and methods H and Y of class B are inaccessible through that A1 pointer. A pointer of type B is necessary to access instance variable K and methods H and Y that are defined upon class B. For example, if an object of class B is pointed to by an A1 pointer, then many object-oriented compilers will not allow a call to method H using an A1 pointer. Thus, it is often desirable to change the type of a pointer.
To remedy this situation, the known technique of "casting" is used. In a specific technique called down-hierarchy casting, or "down casting" (also "narrowing"), the A1 pointer that actually points to an object of class B is converted to a B type of pointer. For example, in the C++ object-oriented programming language, this down cast operation may be written as: B*=dynamic.sub.-- cast&lt;B*&gt;(A1*). This down cast operation takes the A1 pointer, and if it actually points to an object of class B, then the pointer is converted into a pointer of type B. Down casting is useful primarily to get at methods that are defined in a subclass such as class B, and also to reach additional semantics such as new variables that are defined in a subclass. Also, down casting is used to determine if an object really is of class B; the logic of the program may depend upon it. In other words, if an A1 pointer is being used, it may be useful to know if that A1 pointer is actually pointing to an object of class A1, or to an object of class B. One technique of implementing down casting within the context of a distributed object system is described in commonly-assigned, pending U.S. patent application Ser. No. 08/408,633, filed Mar. 22, 1995, now U.S. Pat. No. 5,793,965, the disclosure of which is incorporated herein by reference.
Another type of cast operation that is useful is a cross-hierarchy cast or "cross cast." A cross cast is useful when multiple inheritance is present in a programming language. In the example of FIG. 1, different sets of variables and methods are defined separately in class A1 and in class A2. Class B, however, inherits both of these sets of functionalities so that any object of class B inherits both as well. If an object of class B is pointed to by an A1 pointer, it may be useful to know whether that object of class B also inherits from class A2. In this cross cast operation, the static type is A1 (because that is the type of the pointer), the dynamic type is B because that is the actual class of the object, and the target type is A2 because that is the class that is the potential parent class of the object of class B. In the cross cast operation, it is determined whether the object of class B does in fact inherit from class A2. If so, then the A1 pointer that points to the class B object is converted into an A2 pointer. A cross cast operation is useful for the same reasons as a down cast, namely to get at functionality within class A2, and because the logic of the program may require knowing from which classes a particular object inherits. In another example, consider another defined class A3 that is not a parent class of class B, and again assume a pointer to an object of class B that is an A1 pointer. A cross cast operation from class A1 to the target type of class A3 would fail because an object of class B does not inherit from class A3.
Thus, in object-oriented languages, it is possible for the actual class of an object to be different from the static type of the reference pointer to that object, and to also be different from the target type desired. At times, the programmer must determine the actual class of the object and may wish to change the static type of the pointer to that object. These cast operations (down cast or cross cast) are also termed run time type identification (RTTI) operations. Examples of RTTI include the "instance.sub.-- of" operator in the Java programming language and the "dynamic.sub.-- cast" operator in C++. Such type identification is also described in "Inside the C++ Object Model" by Stanley B. Lippman, Addison Wesley, 1996, and in "The Design and Evolution of C++" by Bjarne Stroustrup, Addison Wesley, 1994, the disclosures of which are incorporated herein by reference. One implementation of type identification used by applicants is described in the document "The C++ Application Binary Interface," the disclosure of which is incorporated herein by reference. However, there are problems associated with these cast operations in object-oriented programming languages.
FIG. 2 illustrates symbolically a prior art object 60 that is an instance of class B 30. Object 60 includes an A1 part 64, an A2 part 66 and a B part 68. Each part of object 60 corresponds to the parent class from which class B inherits, or to class B itself. For example, A1 part 64 includes a virtual pointer 70 to a virtual table 72 that references the methods F and G of class A1. Virtual pointer 70 is also shared with class B in that virtual table 72 also includes references to methods F, H and Y that are defined upon class B. For those functions F and Y of class B that override their corresponding functions in parent classes, virtual table 72 contains a reference to the overriding function of class B. A1 part 64 also includes I variable 74 and J variable 76.
A2 part 66 includes virtual pointer 78 to a virtual table 80 that includes references to the methods defined upon class A2. A separate virtual pointer 78 is used within object 60 because of the multiple inheritance. A2 part 66 also includes instance variables M 82 and N 84. B part 68 includes memory space for instance variable K 86 defined on class B.
Thus, object 60 which is an instance of class B contains a specific part for each of its parent classes (also known as sub-objects). Depending upon which type of pointer is pointing to object 60, it may point to any one of these sub-objects. For example, because B pointer 92 references the complete object 60, it points to the very beginning of object 60. In a similar fashion, A1 pointer 90 points to the beginning of the A1 sub-object 64, which in this case coincides with B pointer 92. A2 pointer 94 points to the beginning of the A2 sub-object 66 within the overall object 60. A dynamic cast operation is performed by adjusting the values of these pointers. For example, performing a down cast from an A2 pointer to a B pointer involves changing the location to which A2 pointer 94 points to the location to which B pointer 92 points. This adjustment of pointers occurs, if, in fact, the down cast or cross cast is successful. And while a downcast from A1 to B does not require a change in the pointers' value, the down cast operation is still useful to check whether the down cast operation is successful (i.e., whether the object is really of type B).
As shown in FIG. 2, multiple inheritance in an object-oriented programming language such as C++ leads to the need for multiple virtual tables. In general, the number of necessary virtual tables corresponds to the number of base classes from which class B might inherit. Another effect on the object model due to multiple inheritance is the need to adjust an object pointer when a function is being called. For example, if A2 pointer 94 is being used to point to object 60 (which really is an instance of class B), but method Y is being called, the A2 pointer needs adjustment. This adjustment is necessary because the method Y defined upon class B has overridden the method Y from class A2. Thus, even though A2 pointer 94 is used to point to object 60, when method Y is called the user expects method Y 38 (defined on class B) to be called, and method Y 38 expects as an implicit argument a pointer to object 60 that is of type B (because method Y 38 is defined upon class B). A variety of techniques exist for converting an A2 pointer in this situation to a B pointer. One technique adds an offset to each virtual table to provide an offset from the original pointer to the correct pointer. Another technique uses a locally generated function called a "thunk" that is used by each virtual table to adjust the object pointer before it calls the desired function. These above techniques adjust the pointer being used to reference an object so that the function being called has the correct type of pointer.
Multiple inheritance in an object-oriented programming language can also lead to other difficulties with cast operations. For example, FIG. 3 illustrates a prior art class hierarchy tree 100 showing a possible class hierarchy in the C++ programming language. In this example, class A 102 and class A1 104 are parent classes for both class B 108 and class C 112. Class A1 106 is also a parent class for class D 110, which in turn is a parent of class C 112. In this style of default inheritance in C++ (termed "nonvirtual"), hierarchy 100 has multiple copies of the same base class A1, namely A1 104 and A1 106. In this example, an object of class C 112 will have a separate sub-object for class A1 104 and a separate sub-object for class A1 106. This type of inheritance is more complicated because more classes must be represented within an object (as sub-objects), and because there is more ambiguity about what "class A1" refers to when there is more than one sub-object named A1 within an object. Cast operations are more difficult because of the multiple sub-objects of the same class; sometimes such a situation should lead to an error.
To further complicate matters, C++ also has an additional inheritance scheme termed "virtual inheritance" (the default inheritance in other languages). In this inheritance scheme, each mention of a class such as A1 only generates one sub-object within an object. In other words, even though class hierarchy 100 may reference class A1 104 and class A1 106, only a single representation of class A1 will be present within an object of type C (in the form of a single A1 sub-object). The occurrence of both of these types of inheritance schemes within the C++ programming language leads to difficult and costly implementations for cast operations. Indeed, other languages with similar inheritance schemes likewise experience costly cast operations.
Another difficulty with cast operations in object-oriented programming languages is the implementation of an inheritance graph used to implement cast operations. For example, C++ uses a directed acyclical graph (DAG) to remedy the difficulties associated with its two kinds of inheritance. In the example of C++, a DAG is built at compile time and is then accessible at run time to help perform cast operations. A tree walking algorithm is used at run time, but this algorithm is recursive and varies exponentially as the square of the depth of the class hierarchy tree. Accordingly, the algorithm is complex and expensive, resulting in a very slow implementation. Furthermore, such an algorithm used with a DAG generates an extremely large data structure that takes up enormous space in memory. Furthermore, only one DAG is typically created for class C 112. However, with the shared libraries in use in modern programming, it can be extremely complex and expensive to implement cast operations in these situations. Aside from C++, other object-oriented programming languages that use costly inheritance graphs are Eiffel and Common Lisp Object System (CLOS).
Therefore, it would be desirable to have a technique for executing cast operations that determines not only if it is a legal cast operation, but also how much an object pointer must be adjusted to access the correct sub-object within an object. It would further be desirable for such a technique to improve upon the DAGs and similar techniques used in object-oriented languages for implementing cast operations.